# 子函数：筛选结果
def filter_solutions(init_line, solutions):
    # 循环solutions，判断每个solution是否匹配init_line
    # 记录下标
    error_list = []
    for i in range(len(solutions)):
        # 循环每个位置，判断是否匹配init_line
        # 不匹配的，记录下标
        p = True
        for j in range(len(solutions[i])):
            if init_line[j] != -1 and init_line[j] != solutions[i][j]:
                # 其实是0和1的比较
                p = False
                break
        if not p:
            error_list.append(i)

    # 删除所有不匹配的solution
    error_list.reverse()
    for i in error_list:
        solutions.pop(i)

    return solutions


# 子函数：找位置递归
def rec_find(size, line_nums, line_now, solutions):
    # 找到追加 结构数组
    # size：寻找的数组长度
    # line_nums：绘图值
    # line_now：之前的绘图状态
    # solutions：结果数组
    # 判断line_nums是否空值，如果空值，追加完成的结果
    if not line_nums:
        new_solution = line_now + [0 for i in range(size)]
        solutions.append(new_solution)
        return
    # 判断长度是否满足，如果不满足，直接返回
    if size < sum(line_nums) + len(line_nums) - 1:
        return
    # 循环找解，并进入下一层递归
    p = line_nums[0]
    for i in range(size - p + 1):
        # new_line = line_now.copy() + [0 for j in range(i)]
        # new_line += [1 for j in range(p)]
        # new_size = size - p - i
        add_line = [0 for j in range(i)] + [1 for j in range(p)]
        new_size = size - p - i
        if len(add_line) < size:
            add_line += [0]
            new_size -= 1
        new_line = line_now.copy() + add_line
        rec_find(new_size, line_nums[1:], new_line, solutions)


# 函数 : 计算单行可能性
def line_solutions(size, init_line, line_nums):
    # size: 一维数组大小
    # init_line: 数组初始状态
    # line_nums: 数组的绘图值
    resu_list = []  # 记录所有可能的结果
    # 计算所有可能性
    # 递归查找
    rec_find(size, line_nums, [], resu_list)
    # 筛选结果
    filter_solutions(init_line, resu_list)
    return resu_list


try_solution = line_solutions(5,
                              [-1, -1, 0, -1, -1],
                              [1, 1])

# def rec_find(size, line_nums, line_now, solutions):
# try_solution = []
# rec_find(5,
#          [1, 1, 1],
#          [1, 0, 1, 0, 0],
# try_solution)

# for i in try_solution:
#     print(i)
